package com.lwx.algorithm.chapter6;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 完全平方数
 */
public class Offer279Two {
    public int numSquares(int n) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(n, 0));
        while (!queue.isEmpty()){
            Pair current = queue.poll();
            int num = current.getNum();
            int step = current.getStep();
            if(num == 0) return step;
            for (int i = 1; num-i*i > 0; i++) {
                queue.offer(new Pair(num - i*i, step+1));
            }
        }
        return 0;
    }
    class Pair{
        int num;
        int step;

        public Pair(int num, int step) {
            this.num = num;
            this.step = step;
        }

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        public int getStep() {
            return step;
        }

        public void setStep(int step) {
            this.step = step;
        }
    }
}
